﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Inspired.Euler
{
    /// <summary>
    /// A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:
    /// 
    /// 1/2	= 	0.5
    /// 1/3	= 	0.(3)
    /// 1/4	= 	0.25
    /// 1/5	= 	0.2
    /// 1/6	= 	0.1(6)
    /// 1/7	= 	0.(142857)
    /// 1/8	= 	0.125
    /// 1/9	= 	0.(1)
    /// 1/10	= 	0.1
    /// Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
    /// 
    /// Find the value of d  1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
    /// </summary>
    public static class Problem026
    {
        /// <summary>
        /// Find the value of d < 1000 for which 1/d contains the longest recurring cycle.
        /// </summary>
        /// <returns></returns>
        public static long Solve()
        {
            return
                Extensions.GetPrimes()
                    .TakeWhile(i => i < 1000)
                    .Select(prime => new { Number = prime, Lambda = BrentCycleDetection((int)prime) })
                    .OrderByDescending(pair => pair.Lambda)
                    .First()
                    .Number;
        }

        // http://en.wikipedia.org/wiki/Cycle_detection
        static int BrentCycleDetection(int i)
        {
            int power = 1, lam = 1;
            int tortoise = 1 / i;
            int tortoiseRem = (1 % i) * 10;
            int hare = tortoiseRem / i;
            int hareRem = (tortoiseRem % i) * 10;
            while (tortoise != hare || tortoiseRem != hareRem)
            {
                if (power == lam)
                {
                    tortoise = hare;
                    tortoiseRem = hareRem;
                    power *= 2;
                    lam = 0;
                }
                hare = hareRem / i;
                hareRem = (hareRem % i) * 10;
                lam++;
            }
            //if (lam > cycle)
            //{
            //    cycle = lam;
            //    numLongestRecurring = i;
            //}
            return lam;
        }
    }
}
